1. Technical Field
The invention disclosed broadly relates to data processing systems and methods and more particularly relates to cryptographic systems and methods for use in data processing systems to enhance security.
2. Background Art
The following patents and patent applications are related to this invention and are incorporated herein by reference:
B. Brachtl, et al., "Controlled Use of Cryptographic Keys Via Generating Stations Established Control Values," U.S. Pat. No. 4,850,017, issued Jul. 18, 1989, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Control Vectors," U.S. Pat. No. 4,941,176, issued Jul. 10, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Data Cryptography Operations Using Control Vectors," U.S. Pat. No. 4,918,728, issued Apr. 17, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Personal Identification Number Processing Using Control Vectors," U.S. Pat. No. 4,924,514, issued May 8, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Extended Control Vectors," U.S. Pat. No. 4,924,515, issued May 8, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Key Management Using Control Vector Translation," U.S. Pat. No. 4,993,069, issued Feb. 12, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Key Management Using Programmable Control Vector Checking,"0 U.S. Pat. No. 5,007,089, issued Apr. 9, 1991, assigned to IBM Corporation and incorporated herein by reference.
B. Brachtl, et al., "Data Authentication Using Modification Detection Codes Based on a Public One Way Encryption Function," U.S. Pat. No. 4,908,861, issued Mar. 13, 1990, assigned to IBM Corporation and incorporated herein by reference.
D. Abraham, et al., "Smart Card Having External Programming Capability and Method of Making Same," Ser. No. 004,501, filed Jan. 19, 1987, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, "Technique for Reducing RSA Crypto Variable Storage", U.S. Pat. No. 4,736,423, issued Apr. 5, 1988, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "Secure Management of Keys Using Control Vectors with Multi-Path Checking," Ser. No. 07/596,637, filed Oct. 12, 1990, assigned to IBM Corporation and incorporated here by reference.
S. M. Matyas, et al., "Secure Cryptographic Operations Using Alternate Modes of Control Vector Enforcement," Ser. No. 07/574,012, filed Aug. 22, 1990, assigned to IBM Corporation and incorporated here by reference.
S. M. Matyas, et al., "Method and Apparatus for Controlling the Use of a Public Key, Based on the Level of Import Integrity for the Key," Ser. No. 07/602,989, filed Oct. 24, 1990, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas, et al., "A Hybrid Public Key Algorithm/Data Encryption Algorithm Key Distribution Method Based on Control Vectors," Ser. No. 07/748,407, filed Aug. 22, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas et al., "Generating Public and Private Key Pairs Using a Passphrase," Ser. No. 07/766,533, filed Sep. 27, 1991, assigned to IBM Corporation and incorporated herein by reference.
S. M. Matyas et al., "Public Key Cryptosystem Key Management Based on Control Vectors," Ser. No. 07/766,260, filed Sep. 27, 1991, assigned to IBM Corporation and incorporated herein by reference.
The cryptographic architecture described in the cited patents by S. M. Matyas, et al. is based on associating with a cryptographic key, a control vector which provides the authorization for the uses of the key intended by the originator of the key. The cryptographic architecture described in the cited patents by S. M. Matyas, et al. is based on the Data Encryption Algorithm (DEA), see American National Standard X3.92-1981, Data Encryption Algorithm, American National Standards Institute, New York (Dec. 31, 1981), whereas the present invention is based on both a secret key algorithm, such as the DEA, and a public key algorithm. Various key management functions, data cryptography functions, and other data processing functions are possible using control vectors, in accordance with the invention. A system administrator can exercise flexibility in the implementation of his security policy by selecting appropriate control vectors in accordance with the invention. A cryptographic facility (CF) in the cryptographic architecture is described in the above cited patents by S. M. Matyas, et al. The CF is an instruction processor for a set of cryptographic instructions, implementing encryption methods and key generation methods. A memory in the cryptographic facility stores a set of internal cryptographic variables. Each cryptographic instruction is described in terms of a sequence of processing steps required to transform a set of input parameters to a set of output parameters. A cryptographic facility application program (CFAP) is also described in the referenced patents and patent applications, which defines an invocation method, as a calling sequence, for each cryptographic instruction consisting of an instruction mnemonic and an address with corresponding input and output parameters.
Public key encryption algorithms are described in a paper by W. Diffie and M. E. Hellman entitled "Privacy and Authentication: An Introduction to Cryptography," Proceedings of the IEEE, Volume 67, No. 3, March 1979, pp. 397-427. Public key systems are based on dispensing with the secret key distribution channel, as long as the channel has a sufficient level of integrity. In a public key cryptographic system, two keys are used, one for enciphering and one for deciphering. Public key algorithm systems are designed so that it is easy to generate a random pair of inverse keys PU for enciphering and PR for deciphering and it is easy to operate with PU and PR, but is computationally infeasible to compute PR from PU. Each user generates a pair of inverse transforms, PU and PR. He keeps the deciphering transformation PR secret, and makes the enciphering transformation PU public by placing it in a public directory. Anyone can now encrypt messages and send them to the user, but no one else can decipher messages intended for him. It is possible, and often desirable, to encipher with PU and decipher with PR. For this reason, PU is usually referred to as a public key and PR is usually referred to as a private key.
One important feature of a public key cryptographic system is that it provides an improved method of key distribution, particularly in the case of a hybrid cryptographic system where it is desired to distributed DEA keys using the public key cryptographic system. To implement this key distribution feature, each user A, B, etc., has an associated public and private key pair (PUa,PRa), (PUb,PRb), etc. Any user, say B, who wishes to distribute a DEA key K to user A, merely encrypts K with PUa, the public key of A. Since only A has PRa, the private key of A, only A can decrypt and recover K. This ensures that only A (who has PRa) and the sender (who used PUa) have a copy of K. However, to make this protocol secure it is necessary for the sender to prove his or her identity to A. That is, if B is the sender, then B must prove his or her identity to A. Only then will A be sure that the key originated with B. (Note that B is already sure that only A can recover the key.) The means to accomplish this is for B to "sign" K or the encrypted key ePUa(K) or the message, with his or her private key PRb. Messages are signed using a cryptographic variable called a digital signature, as explained below. A method for distributing DEA keys using a public key algorithm is taught in co-pending patent application Ser. No. 07/748,407 ("A Hybrid Public Key/Data Encryption Algorithm Key Distribution Method Based on Control Vectors"), cited in the Background Art.
A corollary feature of public key cryptographic systems is the provision of a digital signature which uniquely identifies the sender of a message. If user A wishes to send a signed message M to user B, he operates on it with his private key PR to produce the signed message S. PR was used as A's deciphering key when privacy was desired, but it is now used as his "enciphering" key. When user B receives the message S, he can recover the message M by operating on the ciphertext S with A's public PU. By successfully decrypting A's message, the receiver B has conclusive proof it came from the sender A. Digital signatures can be produced either by decrypting the data to be signed with the private key, which works well when the data is short, or by first hashing the data with a strong one-way cryptographic function and decrypting the so-produced hashed value with the private key. Either method will work. Thus, in the above described method of DEA key distribution, B sends A two quantities: (1) the encrypted key, ePU(K), and (2) a digital signature e.g., of the form (a) dPR(ePU(K)) or dPR(hash(ePU(K))). A method for producing digital signatures based on the hash of the data to be signed is taught in co-pending patent application Ser. No. 07/748,407 ("A Hybrid Public Key Algorithm/Data Encryption Algorithm Key Distribution Method Based on Control Vectors"), cited in the Background Art. Examples of public key cryptography are provided in the following U.S. patents: U.S. Pat. No. 4,218,582 to Hellman, et al., "Public Key Cryptographic Apparatus and Method;" U.S. Pat. No. 4,200,770 to Hellman, et al., "Cryptographic Apparatus and Method;" and U.S. Pat. No. 4,405,829 to Rivest, et al., "Cryptographic Communications System and Method."
In the above example of DEA key distribution, where B sends A a DEA key K, the method is secure only if A can be sure that K has in fact originated from the party so stated (i.e., K originated from the party who has signed K or ePUa(K) or the message). Suppose that B signs K or hash(K), not ePUa(K) or hash(ePUa(K)), i.e., the signature is of the form dPRb(K) or dPRb(hash(K)). Suppose that the signature is of the form dPRb(hash(K)), so that inverting dPRb(hash(K)) with PUb to recover hash(K) does not reveal the value of K. Now, if an adversary with public and private key pair (PUx,PRx) could substitute PUx for PUa, thus causing B to encrypt K with PUx instead of PUa, then the adversary could defeat security by (1) intercepting ePUx(K) and dPRb(hash(K)), (2) decrypting ePUx(K) with PRx, (3) re-encrypting K with PUa to produce ePUa(K), and (4) sending ePUa(K) and dPRb(hash(K)) to A. In this case, A and B are unaware that the adversary has had a peek at K. If B instead signs ePUa(K) or the hash of ePUa(K), then the attack still works, but is a bit more complicated. However, if an adversary with public and private key pair (PUx,PRx) could substitute PUx for PUa and PUx for PUb, thus causing B to encrypt K with PUx instead of PUa and could cause A to validate the signature dPRx(ePUa(K)) with PUx instead of PUb, then the adversary could defeat security by (1) intercepting ePUx(K) and dPRb(hash(ePUx(K)), (2) decrypting ePUx(K) with PRx, (3) re-encrypting K with PUa to produce ePUa(K), (4) hashing ePUa(K) to form hash(ePUa(K)), (5) decrypting hash(ePUa(K)) with PRx to form digital signature dPRx(hash(ePUa(K))), and (6) sending ePUa(K) and dPRx(hash(ePUa(K))) to A. In this case, A validates dPRx(hash(ePUa(K))) with PUx and thus believes that ePUa(K) originates with B. A and B are unaware that the adversary has had a peek at K.
The methods of attack outlined above are thwarted by ensuring that A has a valid copy of PUb and that B has a valid copy of PUa. The common method for accomplishing this is to use a certification center which permits public keys to be registered with the certification center. The process works like this. A party, say A, produces a key pair (PUa,PRa). PUa is included in a message, often called a certificate. The certificate contains a public key and key-related data such as an identifier of the party creating and registering the key, in this case, party A, a key name, a start and end date and time when the key is active, etc. The certification center also has a key pair (PUcert,PRcert), where PUcert is distributed with integrity, in advance, to each of the other parties in the network serviced by the certification center, i.e., to A, B, C, etc. After the certification center is satisfied that a request for public key registration is "okay" (e.g., that party A is in fact the actual party to whom the to-be-registered public key belongs), then the certification center signs the certificate with its private key PRcert, i.e., the cryptographic quantity dPRcert(hash(certificate)) is produced, and the certificate and digital signature are returned to party A or stored in a central directory. Thereafter, the certificate and digital signature can be used as proof that PUa belongs to party A. For example, party B obtains the certificate and digital signature from party A or from the central directory and validates the signature with PUcert, the public key of the certification center. This proves to B that PUa belongs to A. In like manner, A can obtain and authenticate a digital signature and certificate containing B's public key PUb. This completely thwarts the above attacks wherein an adversary substitutes one public key for another, thereby causing A to use PUx instead of PUb and causing B to use PUx instead of PUa.
In most cryptographic systems, the keys belonging to a cryptographic device are encrypted with a single master key and stored in a cryptographic key data set. The master key is stored in clear form within the cryptographic hardware. The concept of using a single master key to encrypt keys stored in a cryptographic key data set is known as the master key concept. In order to electronically distribute keys from one device to another, e.g., to distribute a data-encrypting key as part of session initiation, each pair of devices shares a unique key-encrypting key under which all distributed keys are encrypted. Thus, a data-encrypting key encrypts many messages. A key-encrypting key encrypts many electronically distributed data-encrypting keys, and so forth. A master key encrypts many key-encrypting and data-encrypting keys stored in a particular system's cryptographic key data set. Key management design principles are discussed in a paper by S. M. Matyas et al. entitled "A key-management scheme based on control vectors," IBM Systems Journal, Volume 30, No. 2, 1991, pp. 175-191.
Most cryptographic systems make use of many different types of keys, so that information encrypted with a key of one type is not affected by using a key of another type. A key is assigned a type on the basis of the information the key encrypts or the use being made of the key. For example, a data-encrypting key encrypts data. A key-encrypting key encrypts keys. A PIN-encrypting key encrypts personal identification numbers (PINs) used in electronic funds transfer and point-of-sale applications. A MAC key is used to generate and authenticate message authentication codes (MACs).
At the time a key is generated, the user or user application determines, from among the range of options permitted by the key management, the form of each generated key. For example, a generated key can be produced (1) in clear form, (2) in encrypted form suitable for storage in a cryptographic key data set, or (3) in encrypted form suitable for distribution to a designated receiving device. Generally, cryptographic systems have different options for generating keys in these different forms. For example, the Generate Key Set (GKS) instruction described in U.S. Pat. No. 4,941,176 (cited in the Background Art) accepts a mode parameter which defines the output forms of a randomly-generated DEA key K. In the present invention, the key types are expanded to include a device key pair used for backup and recovery purposes. Also, at the time a key is generated, the user or user application determines, from among the range of options permitted by the key management, the type and usage of each generated key. Type and usage information are examples of a class of key-related information called control information. For example, in U.S. Pat. Nos. 4,850,017, 4,941,176, 4,918,728, 4,924,514, 4,924,515, and 5,007,089, and IBM dockets MA9-88-033 and BT9-90-018 the control information is embodied within a data variable called the control vector. The control vector concepts taught in these US Patents and IBM dockets is summarized in a paper by S. M. Matyas entitled "Key handling with control vectors," IBM Systems Journal, Volume 30, No. 2, 1991, pp. 151-174. In the case of the device key pair, the control information associated with the PU and PR keys is also stored with the keys within the CF, where its integrity is ensured.
In order for a DEA-based cryptographic system to be made operable, each device must first be initialized with a master key and at least one key-encrypting key. The master key permits keys stored in the cryptographic key data set to be encrypted, and the key-encrypting key establishes a key-distribution channel with at least one other network device. When key distribution is performed in a peer-to-peer environment, each device is initialized with a key-encrypting key for each other device with which it wishes to communicate. However, when key distribution is performed with the assistance of a key-distribution center (KDC) or key-translation center (KTC), each device is initialized with only one key-encrypting key shared with the KDC or KTC. Thereafter, additional key-encrypting keys are distributed electronically and initialized automatically using the KDC or KTC. The key-distribution channel can also be made unidirectional. That is, one key-encrypting key encrypts keys transmitted from a first device to a second device and another key-encrypting key encrypts keys transmitted in the other direction. As stated above, each cryptographic device is initialized with at least one key-encrypting key. Consider the process of installing keys between two devices A and B, where one device, say A, generates a key-encrypting key for installation at both A and B. At device A, a clear key-encrypting key KK is randomly generated, e.g., by coin tossing. The clear KK is then manually loaded into the cryptographic hardware where it is encrypted under the A's master key, or a variant key formed as the Exclusive-OR product of the master key and a control vector. The encrypted value of KK is then stored in A's cryptographic key data set. The clear value of KK is then transported to device B, e.g., using a courier. At device B, KK is manually loaded into the cryptographic hardware where it is encrypted under B's master key, or a variant key formed as the Exclusive-OR product of the master key and a control vector. The encrypted value of KK is then stored in B's cryptographic key data set. The encrypted copies of KK at A and B enable A and B to communicate cryptographically as described in U.S. Pat. No. 4,941,176. U.S. Pat. No. 4,941,176 also provides for the initial key-encrypting key KK to be defined as the Exclusive-OR product of two or more key parts. At device A, each key part is manually loaded into the cryptographic hardware. The separately entered key parts are combined within the hardware to form the final value of KK. Each key part can be transported to the receiving cryptographic device using a separate courier. At device B, each key part is manually loaded into the cryptographic hardware and combined to form the final value of KK.
In a hybrid cryptographic system, the key management is designed so that DEA keys are distributed under the encryption of a public key. That is, B distributes a key to A by encrypting the key under PUa, A's public key. A recovers the key by decrypting the received encrypted key with PRa, A's private key, as described above. Thus, the key-encrypting key or keys manually installed into the cryptographic devices of a DEA-based cryptographic system can now be electronically distributed using a public key algorithm.
Instead of manually installing a public and private key pair (PU,PR) at each device, (PU,PR) is generated inside the cryptographic device. The private key, PR, is stored within the cryptographic hardware or it is encrypted under a master key and stored in a cryptographic key data set. If the public key is to be used for key distribution purposes, then its integrity within the cryptographic network can be assured by registering it at a certification center and receiving a certificate and digital signature, as described above. This allows the cryptographic device to freely distribute the public key to other devices with the assurance that the other devices will accept the public key as genuine. Thus, the keys used with the public key algorithm are handled automatically using electronic means; there is no requirement for manual installation of these keys at the cryptographic devices within the network.
In some cases, the public and private keys belonging to a cryptographic device may be stored in clear form within the cryptographic hardware. As an alternative to this approach, keys may be stored outside the cryptographic hardware, e.g., encrypting the public and private keys with the master key, or a variant key derived from the master key, and storing them in key tokens together with other key-related data (i.e., a control vector), as described in co-pending patent application Ser. No. 07/766,260 ("Public Key Cryptosystem Key Management Based on Control Vectors"). Thus, the prior art describes how, in a hybrid cryptographic system using a public key algorithm, to eliminate (1) couriers and (2) manual entry of clear key-encrypting keys. While this is an improvement over a DEA-based cryptographic system, the prior art does not teach how to eliminate a requirement for manual entry of clear keys altogether. Except in special situations, each cryptographic device will need several, and perhaps many, key pairs to perform the tasks of key management and data management. The most practical means for doing this is to make use of a system master key under which, at least, the private keys of the public key algorithm are encrypted for storage in a cryptographic key data set. It is also argued in co-pending patent application Ser. No. 07/766,260 ("Public Key Cryptosystem Key Management Based on Control Vectors") that it is sometimes advantageous to encrypt the public keys for storage in a cryptographic key data set, even though this is not done to keep the public keys secret. Thus, it would be advantageous for the cryptographic system key management to be designed so that the need for manual entry of keys, including the master key itself, is completely eliminated. This would permit cryptographic systems to be used in places where it is impractical or infeasible for a secret master key to be manually loaded into the cryptographic device. In so doing, cryptographic systems could now be designed so that their initialization is fully automated, i.e., not requiring couriers and not requiring the manual entry of keys by humans.
Also note that if all manual entry of keys could be eliminated, this would allow a potential higher level of security to be established for the system, as no human, authorized or not, would be able to introduce known key values into the system which, if entered, would allow the possibility of off-line decryption of anything encrypted under the known quantity.
However, once a mechanism exists for the automatic generation of a system master key, this implies that the master key is not known to anyone or any device except the cryptographic device in which it is generated. This raises the potential that a cryptographic device may accidentally lose its master key due to a system malfunction (hardware malfunction, lighting strike, etc.) causing the master key to be accidentally erased or unusable. In such an event, the keys under which the master key are encrypted are, for practical purposes, lost. That is, the keys are lost in the sense that there is no way that the cryptographic system can now decrypt them, which is required before the keys may be used or processed within the secure boundary of the cryptographic hardware. Therefore, an automatically generated master key also requires a means for backup and recovery. In many cryptographic systems, such as described in U.S. Pat. Nos. 4,850,017, 4,941,176, 4,918,728, 4,924,514, 4,924,515, and 5,007,089, and co-pending patent applications Ser. No. 07/766,260 ("Public Key Cryptosystem Key Management Based on Control Vectors"), etc., the cryptographic hardware is initialized with configuration data as well as other cryptographic variables, including keys, such as the master key. The configuration data personalizes a device, e.g., uniquely identifies a device and restricts the processing options that the device is permitted to perform, including the possibility of crippling the ability to manually enter keys. Thus, in order for cryptographic devices to be easily recoverable in the event that a master key is lost, a means must be provided that permits the keys and configuration data stored in the cryptographic hardware to be ported from one cryptographic device for recovery in another cryptographic device.